
// 5.最长回文子串
class Solution {
public:
    string longestPalindrome(string s) {
        // 使用动态规划来实现 , 二维DP ,dp[i][j] 表示[ j , i ]位置是否是回文串
        int n = s.size();
        vector<vector<bool>> dp(n,vector<bool>(n));
        int ret_l = 0 , ret_r = 0;
        int ret = 1;
        for(int i = 0 ; i < n ; i++)
        {
            for(int j = 0 ; j <= i ; j++)
            {
                if(s[i] == s[j] && (i == j || j + 1 == i || dp[j + 1][i - 1]))
                {
                    dp[j][i] = true;
                    if(i - j + 1 > ret)
                    {
                        ret = i - j + 1;
                        ret_l = j ,ret_r = i;
                    }
                }
            }
        }
        cout << ret_l << " " << ret_r << endl;
        return s.substr(ret_l , ret_r - ret_l + 1);
    }
};